P3978 [TJOI2015]概率论

一道推式子好题，本来确实是想写题解的，但rqy写得实在是太好了，这里就放出她的题解

我这里补充说明一下$ans=\frac{g_n}{f_n}$的原因：

题目说每种树概率相同，那概率$=\frac{1}{f_n}$

设第$i$种n节点的树有$p_i$个叶子

根据期望的线性性，$ans=\sum\limits_{i=1}^{f_n}\frac{p_i}{f_n}=\frac{\sum\limits_{i=1}^{f_n}p_i}{f_n}$

又因为$\sum\limits_{i=1}^{f_n}p_i=g_n$

所以可得$ans=\frac{g_n}{f_n}$